클레이니 스타

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 클레이니 플러스
3. 예시
4. 일반화
5. 성질
참조

1. 개요

클레이니 스타는 형식 언어 이론에서 문자열 집합에 적용되는 단항 연산이다. 집합 V의 클레이니 스타는 V에 있는 문자열을 0번 이상 연결하여 만들 수 있는 모든 문자열의 집합이며, V*로 표기한다. 클레이니 스타는 멱등원 단항 연산자이며, 클레이니 플러스는 빈 문자열을 포함하지 않는 클레이니 스타를 의미한다. 클레이니 스타는 모노이드에서도 정의되며, 문자열 연결 외에도 다양한 분야에서 응용된다.

2. 정의

집합 V에 대하여, V의 n회 연쇄는 다음과 같이 정의된다.

: $V^0 = \{\varepsilon\}$ (빈 문자열)

: $V^1 = V$

: $V^n = V \circ V^{n-1} = \{uv|u\in V, v\in V^{n-1}\} (n \ge 2)$

V의 클레이니 스타는 다음과 같이 정의된다.

: $V^* = \sideset{}{_{i=0}^\infty}\bigcup V^i = \bigcup_{i \in \N }V^i = \{\varepsilon\} \cup V \cup V^2 \cup V^3 \cup V^4 \cup \ldots.$

여기서 V의 i 거듭제곱은 V를 자기 자신과 i번 연결하는 것을 의미하며, V에 있는 i개의 문자열을 연결하여 만들 수 있는 모든 문자열의 집합이다. 클레이니 스타는 V에 속한 문자열들을 0개 이상 연결하여 만들 수 있는 모든 문자열의 집합을 나타내며, 멱등원 단항 연산자이다. 즉, $(V^{*})^{*}=V^{*}$ 이며, 모든 $i\geq 1$ 에 대해 $(V^{*})^{i}=V^{*}$ 이다.

2. 1. 클레이니 플러스

클레이니 플러스는 빈 문자열을 포함하지 않는 클레이니 스타이다.

:

V^+ = \sideset{}{_{i=1}^\infty}\bigcup V^i = V \cup V^2 \cup V^3 \cup V^4 \cup \ldots. = VV^*

여기서

V

가 빈 문자열을 포함하지 않는다면 클레이니 플러스는 빈 문자열을 포함하지 않는 클레이니 스타와 같다.

:

V^+ = V^* - \{\varepsilon\}

V

가 빈 문자열을 포함한다면 클레이니 플러스는 클레이니 스타와 같다.

:

V^+ = V^*

일부 형식 언어 연구 (예: AFL 이론)에서는 클레이니 스타 연산의 변형인 "클레이니 플러스"가 사용된다.^[3] 클레이니 플러스는 위의 합집합에서

V^{0}

항을 생략한다. 즉,

V

에 대한 클레이니 플러스는 다음과 같다.^[3]

:

V^+=\bigcup_{i \geq 1} V^i = V^1 \cup V^2 \cup V^3 \cup \cdots,

또는

:

V^+ = V^*V.

^[3]

3. 예시

클레이니 스타가 문자열 집합에 적용된 예는 다음과 같다.^[1]

:{ "ab", "c" }^* = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.

클레이니 플러스가 문자 집합에 적용된 예는 다음과 같다.^[1]

:{ "a", "b", "c" }⁺ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

클레이니 스타가 동일한 문자 집합에 적용된 예는 다음과 같다.^[1]

:{ "a", "b", "c" }^* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

클레이니 스타가 빈 집합에 적용된 예는 다음과 같다.^[1]

:∅^* = {ε}.

클레이니 플러스가 빈 집합에 적용된 예는 다음과 같다.^[1]

:∅⁺ = ∅ ∅^* = { } = ∅.

여기서 연결은 결합 법칙과 비교환 법칙을 따른다.

클레이니 플러스와 클레이니 스타가 빈 문자열을 포함하는 단일 집합에 적용된 예는 다음과 같다.^[1]

: 만약 $V=\{\varepsilon\}$ 이면, 각 $i$ 에 대해 $V^{i}=\{\varepsilon\}$ 이므로 $V^{*}=V^{+}=\{\varepsilon\}$ 이다.

4. 일반화

$(M, \cdot)$ 이 모노이드이고, ''V''가 ''M''의 부분 집합일 때, ''V''^*는 ε (빈 문자열)을 포함하고 연산에 닫혀 있는 최소의 집합이다. ''V''^* 자체도 모노이드가 되며, "''V''에 의해 생성된 모노이드"라고 한다. 기호 집합 위의 (이항 연산으로서의 문자열 연결에 의한) 모든 문자열의 집합은 모노이드를 이루므로, 이것은 클레이니 스타의 일반화이다.

클레이니 스타는 다음 조건을 만족하는 집합 ''M''과 ''M'' 위의 이항 연산 " . "을 갖는 모노이드 (''M'', .)로 일반화되기도 한다.^[4]

(폐쇄성) 모든 ''a'', ''b'' ∈ ''M''에 대해, ''a'' . ''b'' ∈ ''M''
(결합 법칙) 모든 ''a'', ''b'', ''c'' ∈ ''M''에 대해, (''a'' . ''b'') . ''c'' = ''a'' . (''b'' . ''c'')
(항등원) 어떤 ε ∈ ''M''이 존재하여, 모든 ''a'' ∈ ''M''에 대해 ''a'' . ε = ε . ''a'' = ''a''

클레이니 스타는 완전 스타 반환의 개념을 통해 *-연산(및 합집합)을 대수 구조 자체에 포함시켜 일반화된다.

5. 성질

$(M, \cdot)$ 이 모노이드라고 가정하고, ε∈M이고 M은 연쇄 연산에 닫혀 있다고 하자. 이때 M의 부분집합 N에 대해 N을 포함하는 최소의 모노이드는 $(N^*, \cdot)$ 이다.

집합 $V$ 가 주어졌을 때, 다음과 같이 정의한다.

: $V^{0}=\{\varepsilon\}$ (빈 문자열만으로 구성된 언어)

: $V^{1}=V$

그리고 각 $i>0$ 에 대해 집합을 재귀적으로 정의한다.

: $V^{i+1}=\{wv: w\in V^{i} \text{ and } v\in V \}$

$V$ 가 형식 언어인 경우, 집합 $V$ 의 $i$ 거듭제곱인 $V^i$ 는 집합 $V$ 를 자기 자신과 $i$ 번 연결하는 것을 줄여서 표현한 것이다. 즉, '' $V^i$ ''는 $V$ 에 있는 $i$ 개의 문자열을 연결하여 나타낼 수 있는 모든 문자열의 집합으로 이해할 수 있다.

$V$ 에 대한 클레이니 스타의 정의는 다음과 같다.

: $V^*=\bigcup_{i \ge 0 }V^i = V^0 \cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots.$

이것은 클레이니 스타 연산자가 임의의 문자열 또는 문자 집합 $V$ 에 대해 멱등원 단항 연산자임을 의미한다. 즉, $(V^{*})^{*}=V^{*}$ 이며, 모든 $i\geq 1$ 에 대해 $(V^{*})^{i}=V^{*}$ 이다.

일부 형식 언어 연구 (예: AFL 이론)에서는 클레이니 스타 연산의 변형인 "클레이니 플러스"가 사용된다. 클레이니 플러스는 위의 합집합에서 $V^{0}$ 항을 생략한다. 즉, $V$ 에 대한 클레이니 플러스는 다음과 같다.

: $V^+=\bigcup_{i \geq 1} V^i = V^1 \cup V^2 \cup V^3 \cup \cdots,$

또는

: $V^+ = V^*V.$ ^[3]

문자열은 이항 연산으로 연결, 항등원으로 ε를 갖는 모노이드를 형성한다. 클레이니 스타는 문자열뿐만 아니라 모든 모노이드에 대해 정의된다.

더 정확히 말하면, (''M'', ⋅)를 모노이드, ''S'' ⊆ ''M''이라고 하자. 그러면 ''S''^*는 ''S''를 포함하는 가장 작은 ''M''의 부분 모노이드이다. 즉, ''S''^*는 ''M''의 항등원, 집합 ''S''를 포함하며, ''x'',''y'' ∈ ''S''^*일 경우 ''x''⋅''y'' ∈ ''S''^*를 만족한다.

또한, 클레이니 스타는 완전 스타 반환의 개념을 통해 *-연산(및 합집합)을 대수 구조 자체에 포함시켜 일반화된다.^[4]

참조

_[1] 웹사이트 Countable sets and Kleene star http://www.nayuki.io[...] 2011-05-10
_[2] 서적 Foundations of Discrete Mathematics Brooks/Cole 1991
_[3] 문서
_[4] 서적 Handbook of Weighted Automata https://archive.org/[...] Springer 2009

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com